package 代码记录.Bit48天集训;

import java.util.Scanner;

/**这两个题不是人做的(很难)
 * 1.合唱团
 * 2.马戏团
 * @author zx
 * @create 2022-07-07 20:17
 */
public class day_47 {
    /**
     问题分解：
     从n个学生中选k个,可以看成：先从n个学生里选择最后1个,后在剩下的里选k-1个,并且让这1个和前k-1个满足约束条件

     学生能力数组记为arr[n+1],第i个学生的能力值为arr[i]
     one表示最后一个人，其取值范围为[1,n];
     left表示第k-1个人所处的位置，需要和第k个人的位置差不超过d，因此
     max{k-1,one-d}<=left<=one-1
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] students = new int[n + 1];//学生能力值数组,第i个人直接对应arr[i]
            for(int i = 1;i < students.length;i++){
                students[i] = sc.nextInt();
            }
            int k = sc.nextInt();
            int d = sc.nextInt();
            long res = helper(students, k, d, n);
            System.out.println(res);
        }
    }
    /**
     * 递推的时候，以dp[one][k]的形式表示
     * 其中：one表示最后一个人的位置,k为包括这个人,一共有k个人
     * 原问题和子问题的关系：dp[one][k]=max{dp[left][k - 1]*students[one],gg[left][k - 1] * students[one]}
     */
    private static long helper(int[] students,int k,int d,int n){
        long[][] dp = new long[n + 1][k + 1];//人直接对应坐标,n和kk都要+1
        long[][] gg = new long[n + 1][k + 1];
        //初始化k = 1的情况
        //one表示最后一个人,其取值范围为[1,n];
        for (int one = 1; one <= n; one++) {
            dp[one][1] = students[one];
            gg[one][1] = students[one];
        }
        //自底向上递推
        for (int i = 2; i <= k; i++) {
            for (int one = i; one <= n; one++) {
                //求解当one和k定的时候，最大的分割点
                long max = Long.MIN_VALUE;
                long min = Long.MAX_VALUE;
                for (int left = Math.max(i - 1, one - d); left <= one - 1; left++) {
                    if (max < Math.max(dp[left][i - 1] * students[one], gg[left][i - 1] * students[one])) {
                        max = Math.max(dp[left][i - 1] * students[one], gg[left][i - 1] * students[one]);
                    }
                    if (min > Math.min(dp[left][i - 1] * students[one], gg[left][i - 1] * students[one])) {
                        min = Math.min(dp[left][i - 1] * students[one], gg[left][i - 1] * students[one]);
                    }
                }
                dp[one][i] = max;
                gg[one][i] = min;
            }
        }
        //n选k最大的需要从最后一个最大的位置选
        long res = Long.MIN_VALUE;
        for (int one = k; one <= n; one++) {
            if (res < dp[one][k]) {
                res = dp[one][k];
            }
        }
        return res;
    }
}
